#include <stdio.h>
#include <time.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct {
    int TableLen;//存储动态数组里面元素的个数
    ElemType *elem;//整型指针
} SSTable;

void ST_Init(SSTable &ST, int lenth) {
    //多申请了一个位置，用来存哨兵
    ST.TableLen = lenth + 1;
    //为数组申请空间lenth + 1个空间
    ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);
    int i;
    srand(time(NULL));//随机数生成,方便测试，考研不考
    for (i = 1; i < ST.TableLen; i++) {//因为第0个是哨兵，所以从1随机
        ST.elem[i] = rand() % 100;
    }
    printf("\n");
}

//打印顺序表
void ST_print(SSTable ST) {
    for (int i = 1; i < ST.TableLen; i++) {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}

int Search_Sequence_table(SSTable ST, ElemType key) {
//    int pos = 0;
//从前往后找
//    for (int i = 1; i < ST.TableLen; ++i) {
//        if (ST.elem[i] == key) {
//            pos = i;
//            break;
//        }
//    }
//    return pos;
/*和上面代码效果一样*/
    ST.elem[0] = key;//将哨兵存在零号位置，作为哨兵，有了这个我们在循环时可以少写一个i>=0
    int i;
    //从后往前找
    for (i = ST.TableLen - 1; ST.elem[i] != key; --i);
    return i;
}

//顺序查找
int main() {
    SSTable ST;
    ElemType key;
    ST_Init(ST, 10);//顺序表初始化
    ST_print(ST);
    printf("Please enter the value you want to find\n");
    scanf("%d", &key);
    int pos;
    pos = Search_Sequence_table(ST, key);
    if (pos) {
        printf("Search successfully,the position is %d\n", pos);
    } else {
        printf("Search failed");
    }
    return 0;
}
